链表——两个链表生成相加链表

Posted on | In ,

题目：假设链表中的每个节点都在0~9之间，那么链表整体就可以表示一个整数，如
9->3->7链表加上6->3链表，最后生成的链表是1->0->0->0。

思考：若将两个链表分别转换成整数相加，最后将和转换成链表，由于链表可能很长，会造成整数溢出，不推荐。

实现：注意最终表的排序是从表尾到表头，不然后面需要用到表头参数的函数就不方便计算了。
方法一：用两个栈

  1. 将两个链表分别存到两个栈中
  2. 只要有一个栈不为空，
    则判断当前位置的元素：栈为空则为0，不为空则为弹出的元素。
  3. 执行相加操作：
    将结果合成链表结构。
  4. 最后两个栈为空了，但还是要判断最高位是否有进位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class AddList {
	/**
	 * 利用栈逆序两个链表，执行相加操作
	 * @param head1
	 * @param head2
	 * @return
	 */
	public static Node addList(Node head1, Node head2) {
		Stack<Integer> s1 = new Stack<>(); // stack中存的是data
		Stack<Integer> s2 = new Stack<>();
		//将链表1所有结点入栈
		while (head1 != null) {
			s1.push(head1.data);
			head1 = head1.next;
		}
		//将链表2所有结点入栈
		while (head2 != null) {
			s2.push(head2.data);
			head2 = head2.next;
		}
		int ca = 0; // 进位
		int n1 = 0; // s1的整数
		int n2 = 0; // s2的整数
		int n = 0; // 相加之后的整数
		Node node = null; //当前计算的节点
		Node pre = null; // 用于保存上次计算的节点
		// 只要有一个栈不为空，就进行相加计算
		while (!s1.isEmpty() || !s2.isEmpty()) {
			n1 = s1.isEmpty() ? 0 : s1.pop(); // 如果栈空则n1=0,
			n2 = s2.isEmpty() ? 0 : s2.pop();
			n = n1 + n2 + ca;
			pre = node; // pre用于保存链表下一个结点
			node = new Node(n % 10);
			node.next = pre; //将node与下一个结点进行链接
			ca = n / 10;
		}
		if (ca == 1) {
			pre = node;
			node = new Node(1);
			node.next = pre;
		}
		return node; // 返回头节点
	}

方法二：利用链表的逆序

  1. 将两个链表逆序
  2. 同步遍历两个逆序后的链表，得到从低位到高位的数字
  3. 执行相加操作，判断是否有进位。同时将值存入新链表。
  4. 当两个逆序链表遍历完后，判断是否还有进位。
  5. 最后将新链表再逆序一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public static Node addList2(Node head1, Node head2) {
		head1 = reverseList(head1);
		head2 = reverseList(head2);
		int n1 = 0;
		int n2 = 0;
		int n = 0;
		int ca = 0;
		Node cur1 = head1; //其实这里不做代换效果一样，因为后面没有在用到原链表
		Node cur2 = head2;
		Node node = null;
		Node pre = null; //表尾
		//只要有一个链表不为空
		while (cur1 != null || cur2 != null) {
			n1 = cur1 != null ? cur1.data : 0;
			n2 = cur2 != null ? cur2.data : 0;
			n = n1 + n2 + ca;
			pre = node;
			node = new Node(n % 10);
			node.next = pre; //让node始终为表头
			//如果将第一个点作为表头pre.next = node;最后指针指向表尾，后面再返回表头很麻烦
			ca = n / 10;
			//将两个链表的指针后移，需要判断链表是否为空
			cur1 = cur1 != null ? cur1.next : null;
			cur2 = cur2 != null ? cur2.next : null;
		}
		if (ca == 1) {
			pre = node;
			node = new Node(1);
			node.next = pre;
		}
		//display(reverseList(node));
		return node;
	}
	//逆序链表
	public static Node reverseList(Node head) {
		if (head == null || head.next == null) { //如果链表为空或只有一个元素
			return head;
		}
		Node pre = null;
		Node next = null;
		while (head != null ){ //这里从头到尾逆序链表
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre; //若while循环已经结束，此时pre为原链表最后一个元素
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
	//显示链表
	public static void display(Node head) {
		while (head.next != null) {
			System.out.print(head.data + "->");
			head = head.next;
		}
		//输出链表的最后一个元素
		for (int i = 0; i < getSize(head); i++) {
			if (head.next == null) {
				System.out.println(head.data);
			}
		}
	}

	// Test
	public static void main(String[] args) {
		Node head1 = new Node(9);
		Node node1 = new Node(3);
		Node node2 = new Node(7);
		head1.next = node1;
		node1.next = node2;

		Node head2 = new Node(6);
		Node node3 = new Node(3);
		head2.next = node3;
		//Test reverseList
		//head1 = reverseList(head1);
		//display(head1);
		Node rst = addList2(head1, head2);
		display(rst);
	}
}

输出：

1
1->0->0->0